package com.fyt.recover.order;

import java.util.*;

public class MyRadixSort {
    public static void radixSort(int[] arr) {
        int max = Arrays.stream(arr).max().getAsInt();

        for (int i = 1; max/i>0 ; i*=10) {
         countSort(arr,i);
        }


        System.out.println(Arrays.toString(arr));

    }

/**
 *  按位进行基数排序,,,坏了好像不得不通过前缀和了, 通过arr中的每一个元素的值来用前缀和找到在排序后应处于的位置
 */

    public static void countSort(int[]arr, int exp){
      int [] count=new int[10];
      int [] temp=new int[arr.length];


           //在temp的对应序列位置中记录该位的数的出现次数
        for (int i = 0; i < arr.length; i++) {
            count[arr[i]/exp%10]++;
        }
        //计算前缀和
        for (int i = 1; i <count.length ; i++) {
            count[i]+=count[i-1];
        }

        //为了不在遍历时覆盖原数据,必须要一个数组来暂存数据; 从后往前遍历,不破坏源数组的稳定性.
        for (int i = arr.length-1; i >=0 ; i--) {
          int x=  count[arr[i]/exp%10]; //排序后应处的位置
            temp[x-1]=arr[i];
            count[arr[i]/exp%10]--;

        }
        System.arraycopy(temp,0,arr,0,arr.length);







    }

}